package 优先算法.递归_搜索与回溯.综合案列.组合总和;

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Solution so = new Solution();
        int[] candidates = {2,3,6,7};
        int target = 7;
        List<List<Integer>> result = so.combinationSum(candidates, target);
        for(List<Integer> i : result){
            System.out.println(i);
        }
    }
}
class Solution {
    List<List<Integer>> ret;
    int target;
    public List<List<Integer>> combinationSum(int[] candidates, int _target) {
        target = _target;
        List<Integer> path = new ArrayList<>();
         ret = new ArrayList<>();
         dfs(candidates, 0,path,0);
         return ret;
    }

    private void dfs(int[] candidates, int pow,List<Integer> path,int sum) {
        if(sum == target){
            ret.add(new ArrayList<>(path));
        }
        for(int i = pow; i<candidates.length;i++){
            if(sum + candidates[i] > target) break;
            path.add(candidates[i]);
            dfs(candidates, i, path, sum + candidates[i]);
            path.remove(path.size()-1);
        }
    }

}